Grokking LinkedIn Coding Interview
Rate this course
Ask Author
Contribute
Back to course home

0% completed

Vote For New Content
Introduction
Who Should Take This Course?
LinkedIn Easy
Find Pivot Index (easy)
Solution: Find Pivot Index
Isomorphic Strings (easy)
Solution: Isomorphic Strings
Second Minimum Node In a Binary Tree (easy)
Solution: Second Minimum Node In a Binary Tree
Minimum Time to Type Word Using Special Typewriter (easy)
Solution: Minimum Time to Type Word Using Special Typewriter
Intersection of Two Arrays (easy)
Solution: Intersection of Two Arrays
Can Place Flowers (easy)
Solution: Can Place Flowers
Valid Perfect Square (easy)
Solution: Valid Perfect Square
Maximum Depth (or Height) of Binary Tree (easy)
Solution: Maximum Depth (or Height) of Binary Tree
Sqrt (easy)
Solution: Sqrt
Valid Palindrome (easy)
Solution: Valid Palindrome
LinkedIn Medium
Rotate List (medium)
Solution: Rotate List
Find Leaves of Binary Tree (medium)
Solution: Find Leaves of Binary Tree
Valid Triangle Number (medium)
Solution: Valid Triangle Number
Valid Parenthesis String (medium)
Solution: Valid Parenthesis String
Edit Distance (medium)
Solution: Edit Distance
Remove All Ones With Row and Column Flips II (medium)
Solution: Remove All Ones With Row and Column Flips II
Reverse Integer (medium)
Solution: Reverse Integer
Triplet Sum to Zero (medium)
Solution: Triplet Sum to Zero
Longest Substring Without Repeating Characters (medium)
Solution: Longest Substring Without Repeating Characters (medium)
Decode Ways (medium)
Solution: Decode Ways
Quadruple Sum to Target (medium)
Solution: Quadruple Sum to Target
Next Permutation (medium)
Solution: Next Permutation
Search in Rotated Array (medium)
Solution: Search in Rotated Array
Word Search (medium)
Solution: Word Search
Remove Nth Node From End of List (Medium)
Solution: Remove Nth Node From End of List
House Robber II (medium)
Solution: House Robber II
Coin Change
Solution: Coin Change
Design Add and Search Words Data Structure (medium)
Solution: Design Add and Search Words Data Structure
Merge Intervals (medium)
Solution: Merge Intervals
Number of Islands (easy)
Solution: Number of Islands
Longest Palindromic Subsequence (medium)
Solution: Longest Palindromic Subsequence
Kth Smallest Number (medium)
Solution: Kth Smallest Number
Maximum Product Subarray (medium)
Solution: Maximum Product Subarray
Same Tree (medium)
Solution: Same Tree
Max Points on a Line (hard)
Solution: Max Points on a Line
Closest Binary Search Tree Value II (hard)
Solution: Closest Binary Search Tree Value II
Word Ladder (hard)
Solution: Word Ladder
Median of Two Sorted Arrays (hard)
Solution: Median of Two Sorted Arrays
Largest Rectangle in Histogram (hard)
Solution: Largest Rectangle in Histogram
Serialize and Deserialize Binary Tree (hard)
Solution: Serialize and Deserialize Binary Tree
Solution: Quadruple Sum to Target

Problem Statement

Given an array of unsorted numbers and a target number, find all unique quadruplets in it, whose sum is equal to the target number.

Example 1:

Input: [4, 1, 2, -1, 1, -3], target=1
Output: [-3, -1, 1, 4], [-3, 1, 1, 2]
Explanation: Both the quadruplets add up to the target.

Example 2:

Input: [2, 0, -1, 1, -2, 2], target=2
Output: [-2, 0, 2, 2], [-1, 0, 1, 2]
Explanation: Both the quadruplets add up to the target.

Constraints:

  • 1 <= nums.length <= 200
  • -109 <= nums[i] <= 109
  • -109 <= target <= 109

Solution

This problem follows the Two Pointers pattern and shares similarities with "Triplet Sum to Zero".

We can follow a similar approach to iterate through the array, taking one number at a time. At every step during the iteration, we will search for the quadruplets similar to Triplet Sum to Zero whose sum is equal to the given target.

Here's a detailed walkthrough of the algorithm:

  1. In searchQuadruplets, the array is first sorted in ascending order. Sorting is important as it allows us to navigate our pointers based on the sum we're calculating and ensures that the generated quadruplets are in a predictable order.

  2. A List named quadruplets is created to store all the quadruplets found.

  3. The algorithm then loops over the array, stopping when there are less than four elements remaining (since we need groups of four).

  4. If the current element is the same as the previous one (and it's not the first), we skip this iteration to avoid duplicate quadruplets.

  5. A nested loop is initiated from the next index of the outer loop. This loop also ensures that the current element isn't the same as the previous one to avoid duplicates.

  6. The searchPairs function is called with the array, target value, indices of the first two elements, and the quadruplets list. This function will find pairs in the array (from second+1 index to the end) whose sum with arr[first] and arr[second] equals the target. Any valid quadruplets found are added to the quadruplets list.

  7. In searchPairs, two pointers left and right are initialized: left to second+1, and right to the last element of the array. It then enters a while loop that continues until left is less than right.

  8. Inside this loop, the sum of the elements at the current four indices (first, second, left, right) is calculated. If this sum equals targetSum, a valid quadruplet is found.

  9. This quadruplet is added to the quadruplets list, and both left and right pointers are moved inward. If the next elements are the same as the current elements of left and right respectively, they are skipped to avoid duplicates.

  10. If the calculated sum is less than targetSum, left is incremented to increase the sum (as the array is sorted), and if the sum is greater than targetSum, right is decremented to decrease the sum.

  11. This process repeats until left and right cross, by which point all possible pairs for the given first and second indices have been examined.

  12. Once searchPairs has processed all possible pairs for the given first and second indices, it returns, and the nested loop in searchQuadruplets continues until all possible starting points for quadruplets have been tried.

  13. Once all possible quadruplets have been considered, searchQuadruplets returns the quadruplets list.

The main function in the code demonstrates usage of the searchQuadruplets function with two test cases. It runs searchQuadruplets with specified arrays and target sums, printing the results to the console.

Algorithm Walkthrough

Let's walk through the algorithm using the example input [4, 1, 2, -1, 1, -3] with a target of 1.

  1. Sort the Array:

    • Input: [4, 1, 2, -1, 1, -3]
    • Sorted Array: [-3, -1, 1, 1, 2, 4]
  2. Initialize Result List:

    • quadruplets = []
  3. First Loop (i = 0):

    • Current Element (arr[i] = -3)
    • Second Loop (j = 1):
      • Current Element (arr[j] = -1)
      • Two Pointers: left = 2, right = 5
  4. Two-Pointer Process:

    • First Sum Calculation:
      • sum = arr[0] + arr[1] + arr[2] + arr[5]
      • sum = -3 + (-1) + 1 + 4 = 1
      • Matches Target: Add [-3, -1, 1, 4] to quadruplets
      • Update Pointers:
        • left = 3
        • right = 4
    • Check Duplicates:
      • Skip duplicates by moving pointers:
        • left moves to 4
        • right moves to 4
    • Second Sum Calculation:
      • Pointers Overlap: End of this pair search
  5. Second Loop (j = 2):

    • Current Element (arr[j] = 1)
    • Two Pointers: left = 3, right = 5
    • First Sum Calculation:
      • sum = arr[0] + arr[2] + arr[3] + arr[5]
      • sum = -3 + 1 + 1 + 4 = 3
      • Greater Than Target: Move right pointer left
        • right = 4
    • Second Sum Calculation:
      • sum = arr[0] + arr[2] + arr[3] + arr[4]
      • sum = -3 + 1 + 1 + 2 = 1
      • Matches Target: Add [-3, 1, 1, 2] to quadruplets
      • Update Pointers:
        • left = 4
        • right = 3
    • Check Duplicates:
      • Skip duplicates by moving pointers:
        • left moves to 4
        • right moves to 3
    • Pointers Overlap: End of this pair search
  6. Second Loop (j = 3):

    • Current Element (arr[j] = 1) (Duplicate)
    • Skip this element to avoid duplicates.
  7. First Loop (i = 1):

    • Current Element (arr[i] = -1)
    • Second Loop (j = 2):
      • Current Element (arr[j] = 1)
      • Two Pointers: left = 3, right = 5
    • First Sum Calculation:
      • sum = arr[1] + arr[2] + arr[3] + arr[5]
      • sum = -1 + 1 + 1 + 4 = 5
      • Greater Than Target: Move right pointer left
        • right = 4
    • Second Sum Calculation:
      • sum = arr[1] + arr[2] + arr[3] + arr[4]
      • sum = -1 + 1 + 1 + 2 = 3
      • Greater Than Target: Move right pointer left
        • right = 3
    • Pointers Overlap: End of this pair search
  8. Second Loop (j = 3):

    • Current Element (arr[j] = 1) (Duplicate)
    • Skip this element to avoid duplicates.
  9. First Loop (i = 2):

    • Current Element (arr[i] = 1)
    • Second Loop (j = 3):
      • Current Element (arr[j] = 1) (Duplicate)
    • Skip this element to avoid duplicates.
  • Final Result: The unique quadruplets are [[ -3, -1, 1, 4], [-3, 1, 1, 2]].

Let's walkthrough the example 1 through diagram below.

Image

Code

Here is what our algorithm will look like:

Java
Saved to Cloud

. . . .

Complexity Analysis

Time Complexity

  • Sorting the array: The algorithm begins by sorting the input array, which takes , where N is the number of elements in the array.

  • Outer loop (i): The first loop runs from i = 0 to i = N-4 (i.e., up to the fourth-to-last element in the array). This loop runs times.

  • Second loop (j): The second loop runs from j = i + 1 to j = N-3 (i.e., up to the third-to-last element in the array). This loop also runs times for each iteration of the first loop.

  • Two-pointer search (left and right): For each iteration of the second loop, the two-pointer technique is used to find the remaining two numbers. The two-pointer search takes time in the worst case.

Overall time complexity: The total time complexity is because we have three nested loops and each one runs in linear time. Thus, the overall time complexity is .

Space Complexity

  • Sorting the array: Sorting requires additional space which is uses .

  • Resultant quadruplets storage: The algorithm uses a list quadruplets to store the resulting quadruplets. In the worst case, there can be quadruplets if many valid quadruplets are found.

  • Auxiliary space: A few additional variables (i, j, left, right, etc.) are used, which require constant space .

Overall space complexity: The space complexity for storing the result is , where K is the number of quadruplets, and can be as large as . Adding the space for sorting, the total space complexity becomes in the worst case.

Quadruple Sum to Target (medium)
Next Permutation (medium)
Mark as Completed

On this page

Problem Statement

Solution

Algorithm Walkthrough

Code

Complexity Analysis

Time Complexity

Space Complexity